/**
 * Created by zhourh on 2018/8/1.
 */
public class ReverseLinkedList {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        System.out.println(new ReverseLinkedList().reverseList2(head));
    }

    public ListNode reverseList(ListNode head) {
        ListNode node = head;
        ListNode nextNode;
        ListNode preNode = null;
        while (node != null) {
            nextNode = node.next;
            node.next = preNode;
            preNode = node;
            node = nextNode;
        }

        return preNode;
    }

    public ListNode reverseList2(ListNode head) {
        if (head == null) {
            return null;
        }

        return reverseList(head, null);
    }

    public ListNode reverseList(ListNode node, ListNode preNode) {
        if (node != null) {
            ListNode nextNode = node.next;
            node.next = preNode;
            return reverseList(nextNode, node);
        }

        return preNode;

    }
}
